package Algorithm.sort;

import java.util.*;

/**
 * 207. 课程表 https://leetcode.cn/problems/course-schedule
 * 题目简述：某门课可能需要先修一门或多门课才能修，问最后能否修完所有课程。（即存在循环依赖则不能修完，否则可以）
 */
public class CanFinish {

    public static void main(String[] args) {
        new CanFinish().canFinish(2, new int[][]{{1,0}});
    }

    /**
     * 思路：拓扑排序。使用一个数组记录每个节点的入度，再使用一个list数组记录每个节点的出度节点。将初始入度为0的节点加入到队列中
     * 循环扫描队列，在每层循环中出队所有节点，将每个0入度节点的所有出度节点的入度减一，若减一后节点入度为0，则将其入队
     * 统计所有入队节点数量，若最终数量等于num，说明所有节点入度最后都可为0，返回true，否则说明存在循环依赖，返回false。
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];//记录每个节点的入度
        List<Integer>[] nextCourseList = new ArrayList[numCourses];//记录每个节点的出度节点
        for (int i = 0;i < numCourses;i++)
            nextCourseList[i] = new ArrayList<>();
        for (int i = 0;i < prerequisites.length;i++) {
            inDegree[prerequisites[i][0]]++;
            nextCourseList[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        Deque<Integer> zeroInDegreeDeque = new ArrayDeque<>();
        for (int i = 0;i < inDegree.length;i++) { //将初始入度为0的节点入队
            if (inDegree[i] == 0)
                zeroInDegreeDeque.add(i);
        }
        int count = 0;
        while (!zeroInDegreeDeque.isEmpty()) { //出队一层0入度节点，扫描入队下一层0入度节点，类似于BFS
            int size = zeroInDegreeDeque.size();
            count += size;
            for (int i = 0;i < size;i++) {
                Integer node = zeroInDegreeDeque.poll();
                for (Integer next : nextCourseList[node])
                    if (--inDegree[next] == 0)
                        zeroInDegreeDeque.add(next);
            }
        }
        return count == numCourses;
    }
}
